public class SolutionBuildTreeByPreAndIno {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    int preindex=0;
    public TreeNode buildTree(int[] preOrder,int[] inOrder){
        return buildTreeChild(preOrder,inOrder,0,inOrder.length-1);
    }
    public  TreeNode buildTreeChild(int[] preOrder,int[] inOrder,int begain,int end){
        if (end<begain){
            return null;
        }
        TreeNode root=new TreeNode(preOrder[preindex]);
        int index=findRootIndex(inOrder,begain,end,preOrder[preindex] );
        preindex++;
        root.left=buildTreeChild(preOrder,inOrder,begain,index-1);
        root.right=buildTreeChild(preOrder,inOrder,index+1,end);
        return root;
    }
    public int findRootIndex(int[] inOeder,int begain,int end,int key){
        for (int i = begain; i <end ; i++) {
            if(inOeder[i]==key){
                return i;
            }

        }
        return -1;
    }
}
